/*************************************************************************
Program Name: bst.h
Des: this is the header file that contains the prototype for the Criminal
database
Author: Alberto De Pena
Due Date: 12/12/09 @ 11:55pm
*************************************************************************/

#include <fstream>
#include <string>
using namespace std;

//introduce the Node identifier so a Node* can be typedef'd
struct Node;
struct CriminalData;

const int MAX = 8;

typedef CriminalData TreeType;
typedef Node* TreePointer;

struct CriminalData
{
	string Name;
	string Attribute[MAX];
	int AttributeCount;
};

//define a node in a Bst
struct Node
{
	TreeType info;
	TreePointer left, right;
};

class Bst
{
public:
	//Constructor
	Bst();
	//Makes a copy of the Constructor 
	Bst(Bst &);
	//Destructor
	~Bst();
	//Returns the Root to make sure that the tree is empty
	bool Empty();
	//Returns true if the copy was successfully made
	void CopyTree(TreePointer);
	//Prints the criminals that match the given attributes
	void Print(ostream&);
	//Creates dynamic memory and stores the criminals into the created nodes
	bool Insert(TreeType);
	//Cuts out the criminals that do not have the desired attributes
	void Prune(string);
	
private:
	//Deletes a node that only points to another node
	void DeleteTwoChild(TreePointer);
	//Utilizes Post-Order Traversal to destroy all the nodes in a tree
	void PostOrderDestroy(TreePointer);
	//Deletes a node that does not point to any other nodes
	void DeleteLeaf(TreePointer, TreePointer);
	//Utilizes In-Order Traversal to Print out nodes in alphabetic order
	void InOrderPrint(TreePointer, ostream&);
	//Deletes a node that points to two other nodes
	void DeleteOneChild(TreePointer, TreePointer);
	//Returns true if a desire attribute is found in the attribute array, returns
	//false otherwise
	bool AttributeNotFound(TreePointer, string);
	//Utilizes Post-Order to delete the nodes that do not have the desire attributes
	void PostOrderPrune(string, TreePointer, TreePointer);
	//Creates a object calles Root typedef'd
	TreePointer Root;
};